package com.leetcode;

import java.util.*;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-30 19:04
 * @version: 1.0
 * @description: 最大频率栈
 *  设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
 *  栈： 后进显出
 *  思路：两个map 一个记录 每个元素入栈的频率， 一个用来维护每个频次组中的 栈内数据信息
 *  数据出栈时，肯定是从批次最好的栈先弹出，
 **/
public class FreqStack {

    Map<Integer,Integer> freq ;// 每个元素频率栈
    Map<Integer, Deque<Integer>> group;
    int maxFreq;


    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxFreq = Integer.MIN_VALUE;
    }

    public void push(int val) {

        freq.put(val,freq.getOrDefault(val,0) + 1);
        group.putIfAbsent(freq.get(val),new ArrayDeque<>());
        group.get(freq.get(val)).push(val);
        maxFreq = Math.max(maxFreq,freq.get(val));

    }

    public int pop() {

        Integer val = group.get(maxFreq).peek();
        freq.put(val, freq.get(val) - 1);
        group.get(maxFreq).pop();
        Deque<Integer> deque = group.get(maxFreq);
        if (deque.isEmpty() && maxFreq > 1) {
            maxFreq--;
        }
        return val;

    }

    public static void main(String[] args) {
        FreqStack freqStack = new FreqStack();
        freqStack.push (5);//堆栈为 [5]
        freqStack.push (7);//堆栈是 [5,7]
        freqStack.push (5);//堆栈是 [5,7,5]
        freqStack.push (7);//堆栈是 [5,7,5,7]
        freqStack.push (4);//堆栈是 [5,7,5,7,4]
        freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }
}
